\section{Introduction}
\subsection{Background and Problem Statement}
Radio Frequency Identification (RFID) has been widely used in many applications such as inventory management, object tracking, and localization \cite{JiaLiuINFOCOM14}.
%
For example, Hong Kong International Airport, where the average daily cargo tonnage in May 2010 was 12K tonnes and has been on the rise, uses RFID system to track shipment \cite{HKcargo}.
%
An RFID system consists of readers and tags.
%
A reader interrogates a set of tags and the tags respond with their IDs over a shared wireless medium.
%
A tag is a microchip with an antenna in a compact package that has limited computing power and communication ranges.
%
There are two types of RFID tags: passive tags, which do not have their own power sources and are powered up by harvesting the radio frequency energy from readers, and active tags, which have their own power~sources.

%%
This paper concerns the problem of \emph{multi-category RFID estimation}. Given a set of RFID tags, where in practice each tag's 96-bit ID consists of two fields, a category ID and a member ID, we want to quickly and accurately estimate the number of tags in each category.
%
The category ID contains categorical information such as the manufacture and the type of the product.
%
The member ID identifies a specific product.
%
Multi-category RFID estimation has many applications such as stock monitoring (\eg, monitoring the quantity of which product is lower than a threshold so that they can be stocked timely).
%
We formally formulate this problem as follows: given $\lambda$ categories of RFID tags, $C_1, C_2, \cdots, C_{\lambda}$, whose cardinalities are denoted by $n_1, n_2, \cdots, n_\lambda$, respectively, a confidence interval $\alpha\in (0,1]$, and a required reliability $\beta\in [0,1)$, we want to estimate the number of tags in each category using one or more readers, where for each $1 \leq i \leq \lambda$, we have $P\{|\hat{n_i}-n_i|\leq n_i\alpha\}\geq\beta$.

%%
\Comment{
A multi-category RFID estimation protocol should satisfy three additional requirements.
%
First, it should be standard compliant; otherwise, it will be difficult to be deployed.
%
Second, it should preserve the privacy of tags by not reading their member IDs.
%
Third, it should work with both a single-reader and multiple-reader environments.
%
As the communication range between a tag and a reader is limited, a large population of tags is often covered by multiple readers whose regions often overlap.
}

\subsection{Limitations of Prior Art}
%
To the best of our knowledge, there is no dedicated effort on our multi-category RFID estimation problem.
%
The closest work to ours is top-$k$ category RFID estimation \cite{infocomXieLei}, which outputs the top-$k$ largest categories, and multi-category RFID monitoring \cite{BoShenMobihoc08, ShigangInfocomMultiGroup}, which outputs the categories whose sizes are above/below a predefined threshold value.
%
The top-$k$ category RFID estimation protocol can be stretched to address our multi-category RFID estimation problem if we choose $k$ to be the number of categories (\ie, $k=\lambda$); however, we have observed that its estimation speed is slow as we will show in our experimental results.
%
Multi-category RFID monitoring cannot output the estimated size of each~category.

%%
We could use RFID identification and estimation protocols to address our multi-category RFID estimation problem; however, they are not efficient for this purpose.
%
RFID identification protocols can read the IDs of all tags and thus obtain the accurate number of tags in each category.
%
However, the identification speed is much slower than estimation.
%
The typical RFID identification throughput is only about 100 tags per second \cite{ISO18000}.~Furthermore, the identification process does not preserve the privacy of tags as the tag IDs are breached.
%
In many applications, people do not want to leak their tag IDs, such as those for passports.
%
Existing RFID estimation protocols (\eg, \cite{AlexMobicom12Everybit, li2010energy, AnonymousTracking, kodialam2006fast, ChenMobicom}) can only estimate the total number of tags in a population regardless of their categories.
%
To use such protocols to address our multi-category RFID estimation problem, we need to separately execute such protocols on each category.
%
Specifically, the reader can send the \texttt{SELECT}
command \cite{epcglobal2004radio} to activate the tags of a specific category to let them participate the estimation protocol, while keeping the tags of other categories inactive.
%
For advanced RFID estimation protocols (\eg, \cite{AlexMobicom12Everybit, ChenMobicom}), the estimation time is determined by the given confidence interval $\alpha\in (0,1]$ and required reliability $\beta\in [0,1)$, regardless of tag population sizes.
%
Thus, if~we~use existing RFID estimation protocols to address our problem, the estimation time grows linearly with the number of categories, which is inefficient.

\subsection{Proposed Approach}
%
In this paper, we propose a protocol called \underline{S}imultaneous \underline{E}stimation for \underline{M}ulti-category RFID systems (SEM).
%
To achieve simultaneous RFID estimation over multiple categories, we use single-one Manchester coding, which is supported by the ISO 18000-6 \cite{ISO18000} RFID standard, to encode category IDs.
%
Given $\lambda$ categories, we re-encode the ID of the $i$-th category as a vector of $\lambda$ bits where exactly the $i$-th bit is 1 and all other bits are 0s.
%
For example, given 3 categories, we can encode them as 100, 010, and 001, respectively.
%
%To re-encode the category IDs of the tags in category $C_i$, the reader can issue the \texttt{SELECT} command to activate the tags in this category and re-encode their category IDs.
%
When querying the category IDs of two tags, which are in the $i$-th category and the $j$-th category, respectively, if $i=j$, then the reader obtains a vector of $\lambda$ bits where exactly the $i$-th bit is 1 and all other $\lambda -1$ bits are 0s; if $i \neq j$, then the reader obtains a vector of $\lambda$ bits where exactly the $i$-th bit and the $j$-th bit are collisions and all other $\lambda -2$ bits are 0s.
%
Specifically, as illustrated in Figure \ref{ManchesterCode}, 1 is coded as a falling edge and 0 is coded as a rising edge. The data transmission in a slot is well synchronized by the beacon signal from the reader \cite{XieLeiIC3NRuleChecking}.
%
If all tags transmit 0 (or 1) at the same time, the reader can successfully recover the bit as 0 (or 1); otherwise, the reader will detect a bit collision $x$.
%
Thus, from the bit vector that the reader obtains, we know exactly which categories of tags responded in this slot.
%
Note that Manchester coding is supported by the RFID standard ISO 18000-6 \cite{ISO18000} for detecting bit-level collisions \cite{YuanHsinTIndusI, YuanChengTMC}.

\begin{figure}[htb]
\centerline{\includegraphics[scale=0.35]{Fig/ManchesterCode}}
\vspace{-0.1in}
\caption{Single-one Manchester Coding}
\label{ManchesterCode}
%\vspace{-0.1in}
\end{figure}

%%
Our estimation protocol is based on the standard Framed Slotted Aloha protocol \cite{lee2005enhanced} for MAC layer communication.
%
First, the RFID reader initializes a slotted time frame by broadcasting a binary request $\langle \delta,f \rangle$, where $\delta$ is a random seed and $f$ is the frame size (\ie, the number of slots in the forthcoming frame).
%
Each tag randomly chooses a slot in the frame to reply its category ID.
%
Specifically, each tag initializes its slot counter $sc=H(ID,\delta)\mod f$, which follows a uniform distribution within $[0,f-1]$.
%
The reader broadcasts \texttt{QueryRep} command at the end of each slot to inform every tag to decrement its slot counter $sc$ by 1.
%
In each slot, a tag responds to the reader once its slot counter $sc$ becomes 0.
%
The duration of a slot for transmitting $\gamma$-bit data, denoted as $t_{\gamma}$, is $\tau_w+\gamma\times\tau_b$, where $\tau_w$ is the waiting time and $\tau_b$ is the time for transmitting 1-bit data.
%
Typically, $\tau_w=302us$ and $\tau_b=18.8us$ \cite{XieLeiIC3NRuleChecking, QiaoMobihoc11}.
%
At the end of each frame, the reader obtains an array of $f$ ternary strings where each ternary string has $\lambda$ bits and each bit has a value of $0$, $1$, or $x$.
%
We call this array a \emph{physical frame}.
%
For the $\lambda$-bit ternary string $t_i$ of the $i$-th slot, for each $1 \leq j \leq \lambda$, if $t[j]=0$, then there is no tag in category $C_j$ responded in the slot; if $t[j]=1$, then only tags in category $C_j$ responded in the slot; if $t[j]=x$, then there are at least two tags, one in category $C_j$ and one not in category $C_j$, responded in the slot.
%
Thus, from this physical frame, we can obtain $\lambda$ \emph{logical frames}, one for each category, where the logical frame for category $C_i$ is the same as the physical frame that the reader could obtain if the tag population only contains the tags in $C_i$.
%
Figure \ref{basicIdea} shows an example of obtaining $\lambda$ logical frames from a physical frame.
%
For example, for the third slot, the ternary string $xxx$ is the collision result of three Manchester codes: 100, 010, and 001.

\begin{figure}[htb]
\centerline{\includegraphics[scale=0.35]{Fig/basicIdea}}
\vspace{-0.1in}
\caption{From one physical frame to $\lambda$ logical frames}
\label{basicIdea}
\end{figure}

%%
We now zoom into the logical frame for category $C_i$.
%
For each slot, we either have the category ID or empty.
%
By denoting the slot with the category ID as 1 and the slot with empty read as 0, we obtain a $f$-bit bit vector.
%
Figure \ref{basicIdea} shows three bit vectors that we obtain.
%
The intuition is that for each category, the less tags it contains, the more 0s the corresponding bit vector contains.
%
Thus, for each category, based on the number of 0s in its bit vector, we can estimate the number of tags in the category.

\subsection{Challenges and Proposed Solutions}
%
The first key challenge is to guarantee the required estimation accuracy specified by confidence interval $\alpha\in (0,1]$ and required reliability $\beta\in [0,1)$ for all categories.
%
As the estimation based on one round of our protocol has an inherent variance due to the probabilistic nature, we execute multiple rounds of the protocol to reduce the variance.
%
To achieve guaranteed accuracy, we first calculate the variance of our estimator for one round and the variance of the average estimate in multiple rounds.
%
Then, we use statistical methods to find the minimum number of rounds that can achieve the required accuracy.

%%
The second key challenge is to choose an optimal frame size $f$ that minimizes estimation time.
%
The key factor that impacts estimation time is $f$.
%
We show that the execution time is a convex function with respect to the frame size, which means that the estimation time is long when the frame size is too small or too big.
%
To find the optimal frame size, we propose an efficient binary search based algorithm.

%%
The third key challenge is to deal with categories that vary significantly in size.
%
To minimize the estimation time, categories of small sizes demand a small frame size whereas categories of large sizes demand a large frame size.
%
To~address this issue, we propose to group categories of similar sizes together and execute our estimation protocol for each group separately.
%
Although this introduces more rounds of our estimation protocol, but the estimation time of each group is well optimized as the categories in each group have similar sizes.
%
Such a hybrid approach has smaller estimation time in comparison with the two extreme approaches of estimating each category separately and estimating all categories together.
%
As we do not know category sizes in advance, we propose to adaptively partition the categories based on the execution of previous rounds.

\subsection{Novelty and Advantage over Prior Art}
%
The key technical novelty of this paper is on formalizing the multi-category RFID estimation problem and proposing single-one Manchester coding to achieve simultaneous estimation.
%
The key technical depth of this paper is on the mathematical development of our estimation protocol in addressing the three technical challenges of guaranteeing accuracy, choosing frame sizes, and partitioning categories.
%
The key advantage of our protocol over prior art is on much smaller estimation time and much better scalability with respect to the number of groups.
%
Compared with the approach of estimating each category separately using prior RFID estimation schemes, our protocol is much faster.
%
For example, for a RFID system with more than 50 categories, our protocol uses 3.2 seconds whereas the most recent SCRs protocol takes 29 seconds \cite{ChenMobicom}.
%
As the number of categories increases, the estimation time of our protocol grows slightly whereas that of prior estimation protocols grow linearly.

%%
The remainder of this paper is organized as follows.
%
In Sections \ref{basicProtocol} and \ref{enhancedProtocol}, we present our basic SEM protocol and its optimized version with the adaptive partitioning technique.
%
In Section \ref{performanceEvaluation}, we conduct extensive simulations to evaluate the performance of the proposed protocols.
%
We discuss related work in Section \ref{relatedWork}.
%
Finally, we conclude the paper in Section \ref{conclusion}.














